package 中等.栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每
 * 个字母只出现一次。需保证 返回结果的字典序最小（要求不
 * 能打乱其他字符的相对位置）。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-duplicate-letters/
 * 思路：比如"bcabc"
 * 1，栈为空，b入栈
 * 2，当前元素为c，栈顶为b，c在栈中不存在，c比b大，c入栈
 * 3
 * a，当前元素为a，栈顶为c，a在栈中不存在，a比c小，并且c在后面还会出现，c出栈
 * b，当前元素为a，栈顶为b，a在栈中不存在，a比b小，并且b在后面还会出现，b出栈
 * 4，当前元素为b，栈顶为a，b在栈中不存在，b比a大，b入栈
 * 5，当前元素为c，栈顶为b，c在栈中不存在，c比b大，c入栈
 */
public class 去除重复字母_316 {

    public static void main(String[] args) {

        System.out.println(removeDuplicateLetters("bcabc"));

    }

    /**
     * 贪心+栈
     * a，先判断当前元素是否已经在栈中出现，如果已经出现，直接跳过当前元素
     * 原因：
     * 结果是分段单调递增的，分段是因为，是因为 某个单调递增段的最后一个元素，
     * 在以后不会再遍历到，而题目又要求我们保持选取字母的相对顺序，因此 某个
     * 单调递增段的最后一个元素 必需被放置在现在放置的位置。
     * 如果现在栈中元素[a, c, d, b]，添加元素c
     * 因为是单调递增的，如果将前面的c消除，那么这个结果将会变大，所以直接跳过
     * b，再判断栈顶元素是否后面还会出现,并且判断当前元素是否比栈顶元素小
     * 如果符合条件，则栈顶元素出栈
     * 否则，当前元素入栈
     */
    public static String removeDuplicateLetters(String s) {
        int len = s.length();
        //charAt方法会检查下标是否越界，降低速度
        char[] chars = s.toCharArray();

        //只包含小写字母，去重后最多有26位数
        //该数组表示字母出现的最后一次的下标
        int[] lastIndex = new int[26];
        for (int i = 0; i < len; i++) {
            //'a'-'a'=0,'b'-'a'=1...
            //每一个字母对于lastIndex[]中特定的位置，lastIndex[0]代表a最后一次出现的下标...
            lastIndex[chars[i] - 'a'] = i;
        }
        Deque<Character> stack = new ArrayDeque<>();
        //记录某一个元素是否已经在栈中出现
        boolean[] visited = new boolean[26];
        for (int i = 0; i < len; i++) {
            //判断是否已经在栈中存在，visited数组默认全为false
            if (visited[chars[i] - 'a']) {
                continue;
            }
            //peek方法取得栈顶元素，但不消除栈顶元素，可能有"bcabc"的情况，所以需要循环
            while (!stack.isEmpty() && chars[i] < stack.peekLast() && i < lastIndex[stack.peekLast() - 'a']) {
                //栈顶元素出栈
                Character top = stack.removeLast();
                visited[top - 'a'] = false;
            }
            //当前元素入栈
            stack.addLast(chars[i]);
            //当前元素在栈中设置为存在
            visited[chars[i] - 'a'] = true;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (Character c : stack) {
            stringBuilder.append(c);
        }
        return stringBuilder.toString();
    }

}
